#leetcode题目45：跳跃游戏ii
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：贪心

# 贪心思路：找出下一步能到区间，在这个区间里取出下下一步能到最远的点作为下一步到达的点，从而保证最远的一个距离。
from typing import List
class Solution:
    def jump(self, nums: List[int]) -> int:
        n=len(nums)
        if n<=1:
            return 0
        step=1
        left,right=1,nums[0]

        while right<n-1:
            for i in range(left,right+1):
                if i+nums[i]>=right:
                    right=i+nums[i]
                    left=i+1
            step+=1
        return step

#测试数据
nums=[2,3,1,1,4]
#预期输出：2
solution=Solution()
print(solution.jump(nums))

nums=[2,3,0,1,4]
#预期输出：2
solution=Solution()
print(solution.jump(nums))




